/**
 * Definition for singly-linked list.
 * */
struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };


#include<iostream>
using namespace std;


class Solution {
public:
    void reorderList(ListNode* head) 
    {
        //找到中间结点
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast->next!=nullptr&&fast->next->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* mid=slow->next;
        slow->next=nullptr;

        //将后半部分的链表逆转
        ListNode* prev=nullptr;
        ListNode* cur=mid;
        while(cur)
        {
            ListNode* tmp=cur->next;
            cur->next=prev;
            prev=cur;
            cur=tmp;
        }
        mid=prev;
        
        //合并链表
        ListNode* cur1=head;
        ListNode* cur2=mid;

        while(cur1&&cur2)
        {
            ListNode* temp=cur2;
            cur2=cur2->next;
            temp->next=cur1->next;
            cur1->next=temp;
            cur1=cur1->next->next;
        }

    }
};